package src;

/**
 * @version : 1.0.0
 * @author：jacky
 * @date : 2020/1/19
 * 矩形覆盖
 * 我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。
 * 请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
 */
public class Tem_RectOver {


    //TODO 解题思路
    /*
    不难看出，这也是一个斐波那契问题，这里假设到了n，上一步就有两种情况，在n-1的时候，竖放一个矩形
    在n-2的时候，横放两个矩形，所以总数是f(n) = f(n-1) + f(n-2)
     */
    public int RectCover(int target) {
       if (target<= 0)
           return 0;
           if (target == 1)
           return 1;
       if (target == 2)
           return 2;
       int[] res = new int[target];
       res[0] = 1;
       res[1] = 2;
       for(int i =2;i<= target-1;i++){
           res[i] = res[i-1] + res[i-2];
       }
       return res[target-1];
    }
}
